/**
 * 
 */
package leetCode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhong
 *
 */
public class ReachaNumber {
	public int reachNumber(int target) {
		long t = Math.abs(target);
		int n = (int) Math.ceil((Math.sqrt(1 + 8 * t) - 1) / 2);
		int d = n * (n + 1) / 2 - target;
		return n + (d % 2) * (1 + n % 2);
	}

	public int f(int target, int s) {
		if (target == 0) {
			return 0;
		}
		return Math.min(f(target + s, s + 1), f(target - s, s + 1)) + 1;
	}

	public int f(int target) {
		if (target == 0) {
			return 0;
		}
		return f(target, 1);
	}

	public int reachNumberxx(int target) {
		Queue<Integer> pos = new LinkedList<>();
		pos.add(0);
		if (target == 0) {
			return 0;
		}
		int depth = 1;
		while (!pos.isEmpty()) {
			int size = pos.size();
			for (int i = 0; i < size; i++) {
				int cur = pos.poll();
				int left = cur - depth;
				int right = cur + depth;
				if (left == target || right == target) {
					return depth;
				}
				pos.add(left);
				pos.add(right);
			}
			depth++;
		}
		return -1;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int target = 1000000000;
		System.out.println(new ReachaNumber().reachNumber(target));
	}

}
